'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-03 09:48:14
'''
'''
108. 将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5
'''

from typing import List
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def __init__(self):
        self.list = []
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def recurse_left(nums, left, right):
            if left>right:
                return None
            med = (left+right)//2
            root = TreeNode(nums[med])
            root.left = recurse_left(nums, left, med-1)
            root.right = recurse_left(nums, med+1, right)
            return root
        def recurse_right(nums, left, right):
            if left>right:
                return None
            med = (left+right+1)//2
            root = TreeNode(nums[med])
            root.left = recurse_right(nums, left, med-1)
            root.right = recurse_right(nums, med+1, right)
            return root
        def recurse_rand(nums, left, right):
            if left>right:
                return None
            import random
            med = (left+right+random.randint(0, 1))//2
            root = TreeNode(nums[med])
            root.left = recurse_rand(nums, left, med-1)
            root.right = recurse_rand(nums, med+1, right)
            return root
        
        return recurse_left(nums, 0, len(nums)-1)

    def BSTtoSortedArray(self, root):
        if not root:
            return
        self.BSTtoSortedArray(root.left)
        self.list.append(root.val)
        self.BSTtoSortedArray(root.right)
if __name__ == "__main__":
    solution = Solution()
    nums = [-10,-3,0,5,9]
    print('origin nums is ', nums)
    root = solution.sortedArrayToBST(nums)
    solution.BSTtoSortedArray(root)
    print('after operation, the nums is ', solution.list)
